#include <iostream>
using namespace std;

#include "ProgCommon.h"
#include "Chain.h"


template<class T>
void SelectSort( T a[], int n )
{
    int i, j, k;
    for ( i = 1; i < n; i++ ) {
        k = i;
        for ( j = i + 1; j <= n; j++ ) {
            if ( a[j] < a[k] )
                k = j;
        }
        if ( k != i )
            Swap( a[i], a[k] );
    }
}

template<class T>
void ShowList( T a[], int from, int to )
{
    cout << "[ ";
    for ( int i = from; i <= to; i++ ) {
        cout << a[i] << " ";
    }
    cout << "]";
}


int main()
{
    PROG_BANNER;
    RAND_SEED;

    int i, j, sz;

    int n = 10;
    int m = 20;
    int k = 5;

    int blen = m / k; // 4
    int rest = m % k;
    if ( rest > 0 ) blen++;

    int **bin = new int*[k+1];
    for ( i = 0; i <= k; i++ ) {
        bin[i] = new int[blen+1];
        bin[i][0] = 0;
    }

    int *pLst = new int[n+1];
    for ( i = 1; i <= n; i++ ) {
        pLst[i] = RandomInt( 1, m + 1 );
        int nr = pLst[i]/blen + 1;
        if ( pLst[i] % blen == 0 ) nr--;
        bin[nr][0]++;
        bin[nr][ bin[nr][0] ] = pLst[i];
    }

    ConSetColor( FG_CYAN );
    printf( "Prog 2: Bucket sort\n" );
    ConSetColor( COLOR_DEFAULT );
    printf( "Random array is: " );
    ConSetColor( FG_GREEN );
    ShowList( pLst, 1, n );
    ConSetColor( COLOR_DEFAULT );
    printf( "\n\n" );

    printf( "Before sort >>\n" );
    for ( i = 1; i <= k; i++ ) {
        sz = bin[i][0];
        printf( " Bin %d : [ ", i );
        for ( j = 1; j <= sz; j++ )
            cout << bin[i][j] << " ";
        printf( "]\n" );
    }

    printf( "\nAfter sort >>\n" );
    for ( i = 1; i <= k; i++ ) {
        sz = bin[i][0];
        SelectSort( bin[i], sz );
        printf( " Bin %d : [ ", i );
        for ( j = 1; j <= sz; j++ )
            cout << bin[i][j] << " ";
        printf( "]\n" );
    }

    int idx = 1;
    for ( i = 1; i <= k; i++ ) {
        sz = bin[i][0];
        for ( j = 1; j <= sz; j++ )
            pLst[idx++] = bin[i][j];
    }

    printf( "\nFianl sorted array is: ");
    ConSetColor( FG_RED );
    ShowList( pLst, 1, n );
    ConSetColor( COLOR_DEFAULT );

    printf( "\n" );
    PROG_BANNER;
    PROG_PAUSE;
    return 0;
}

